The detection of round objects is important for many practical applications. For example, it is useful in industrial applications such as automatic assembly and inspection where many components are round in shape. Further, it may be employed to automatically detect traffic signs, which are circular in most European and Asian countries. Circle detection may also be used in biometric applications for iris recognition to localize the inner and outer boundaries of the iris.
A popular image analysis technique for circle detection is the Hough transform for circles. Hough transforms generate parametric representations of lines in an image; they map an image in real space, which typically specifies image values (e.g., brightness or color) as a function of Cartesian spatial coordinates, onto a Hough space spanned by parameters suitable for the lines or curves of interest. For example, straight lines in a two-dimensional image can be mapped onto a two-dimensional parameter space specifying their direction and distance from the origin of the coordinate system, and circles in a two-dimensional image can be mapped onto a three-dimensional parameter space specifying the center coordinates and radii of the circles.
In a straightforward implementation of the Hough transform for circles (also referred to as the Standard Hough Transform or SHT), a three-dimensional accumulator array for the Hough space spanned by the circle centers (xc,yc) and radii r is maintained, and the pixels in the real-space image that correspond to edges (i.e., lines at which an image parameter such as brightness, color, or depth undergoes a discrete change) are parsed to “vote” for the elements of the accumulator array by incrementing counters stored for the respective elements. In the simplest embodiment, each edge pixel “votes” for all the accumulator array elements that correspond to potential circles including that pixel: for example, looking for circles with radii in the range from rmin to rmax an edge pixel with coordinates (x,y) votes for all elements (xc,yc,r) in the accumulator array that satisfy the equation (x−xc)2+(y−yc)2=r2 with rmin≦r≦rmax. Each edge pixel will, thus, be mapped onto a cone section in the Hough parameter space. For edge points that lie on the same circle in real space (i.e., in the original image), these cone sections intersect at a single point. Circles can, thus, be identified by finding the local maxima in the accumulator array.
The SHT for circles requires significant execution time and a large memory for the Hough accumulator array, typically precluding storage of the array in the internal memory of a microprocessor or microcontroller. Further, it entails frequent, random accesses to the accumulator array, impeding the use of direct memory access (DMA) and cache for typical embedded microcontrollers and digital signal processors (DSPs). Accordingly, various modifications to the SHT that reduce processing and memory requirements have been proposed. For example, exploiting knowledge of the directions of edges in the image, the number of accumulator array elements on which an edge pixel votes can be reduced to those elements that correspond to circle centers on a line perpendicular to the edge (or in a region surrounding that line, to account for inaccurate estimates of the edge direction). Further, instead of using a three-dimensional accumulator array, two or more lower-dimensional arrays may be used in succession. For instance, some techniques detect circles in two stages: a first stage to identify possible centers, and a second stage to estimate the radius for each center. While these modifications can improve the performance of Hough-transform algorithms, they typically do not suffice to facilitate buffering the accumulator array in local memory. Further, two-stage algorithms as used in the prior art do not work efficiently when concentric circles or arcs are present in the image. Therefore, robust techniques that further reduce memory requirements and/or execution time are highly desirable.